#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/*
给出两个整数 n 和 k，找出所有包含从 1 到 n 的数字，且恰好拥有 k 个逆序对的不同的数组的个数。

逆序对的定义如下：对于数组的第i个和第 j个元素，如果满i < j且 a[i] > a[j]，则其为一个逆序对；否则不是。

由于答案可能很大，只需要返回 答案 mod 109 + 7 的值。换言之，求排列组合的个数满足这么多逆序数。

示例 1:

输入: n = 3, k = 0
输出: 1
解释: 
只有数组 [1,2,3] 包含了从1到3的整数并且正好拥有 0 个逆序对。
示例 2:

输入: n = 3, k = 1
输出: 2
解释: 
数组 [1,3,2] 和 [2,1,3] 都有 1 个逆序对。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/k-inverse-pairs-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

class Solution
{
public:
    int kInversePairs(int n, int k)
    {
        const int mod = 1000000007;
        vector<vector<long>> dp(n + 1, vector<long>(k + 1));
        if (k > n * (n - 1) / 2 || k < 0)
            return 0;
        else if (k == 0 || k == n * (n - 1) / 2)
            return 1;
        dp[2][0] = 1;
        dp[2][1] = 1;
        for (int i = 3; i <= n; i++)
        {
            dp[i][0] = 1;
            for (int j = 1; j <= min(k, n * (n - 1) / 2); j++)
            {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                if (j >= i)
                    dp[i][j] -= dp[i - 1][j - i];
                dp[i][j] = (dp[i][j] + mod) % mod;
            }
        }
        return (int)dp[n][k];
    }
};